package exp4;

import static java.lang.Math.max;

public class BinarySearchTree<T extends Comparable<? super T>> {
    private BinaryNode<T> root;

    public BinarySearchTree() {
        root = null;
    }

    public static void main(String[] args) {
        BinarySearchTree<Integer> tree = new BinarySearchTree<>();
        tree.insert(3);
        tree.insert(1);
        tree.insert(4);
        tree.insert(6);
        tree.insert(9);
        tree.insert(7);
        tree.insert(5);
        tree.insert(2);
        // i
        try {
            System.out.println("Number of leaves: " + tree.numberOfLeaves());
        } catch (Exception e) {
            System.out.println(e.getMessage());
        }
        // ii
        System.out.println("Preorder: " + tree.preorderSearch());
        System.out.println("Inorder: " + tree.inorderSearch());
        System.out.println("Postorder: " + tree.postorderSearch());
        // iii
        System.out.println("Height of tree: " + tree.heightOfTree());
        // iv
        System.out.println("Number of node: " + tree.numberOfNode());
    }

    public void makeEmpty() {
        root = null;
    }

    public boolean isEmpty() {
        return root == null;
    }

    public void insert(T x) {
        root = insertRE(x, root);
    }

    private BinaryNode<T> insertRE(T x, BinaryNode<T> t) {
        if (t == null) {
            return new BinaryNode<>(x);
        }
        int compareResult = x.compareTo(t.element);
        if (compareResult < 0) {
            t.left = insertRE(x, t.left);
        } else if (compareResult > 0) {
            t.right = insertRE(x, t.right);
        }
        return t;
    }

    public String preorderSearch() {
        return preorderSearchRE(root);
    }

    private String preorderSearchRE(BinaryNode<T> node) {
        StringBuilder str = new StringBuilder();
        if (node != null) {
            str.append(node.element + " ");
            str.append(inorderSearchRE(node.left));
            str.append(inorderSearchRE(node.right));
        }
        return str.toString();
    }

    public String inorderSearch() {
        return inorderSearchRE(root);
    }

    private String inorderSearchRE(BinaryNode<T> node) {
        StringBuilder str = new StringBuilder();
        if (node != null) {
            str.append(inorderSearchRE(node.left));
            str.append(node.element + " ");
            str.append(inorderSearchRE(node.right));
        }
        return str.toString();
    }

    public String postorderSearch() {
        return postorderSearchRE(root);
    }

    private String postorderSearchRE(BinaryNode<T> node) {
        StringBuilder str = new StringBuilder();
        if (node != null) {
            str.append(inorderSearchRE(node.left));
            str.append(inorderSearchRE(node.right));
            str.append(node.element + " ");
        }
        return str.toString();
    }

    public int numberOfLeaves() throws Exception {
        return numberOfLeavesRE(root);
    }

    private int numberOfLeavesRE(BinaryNode<T> node) throws Exception {
        int ret = 0;
        if (root == null) {
            throw new Exception("The BinarySearchTree is empty");
        }
        if (node.left != null) {
            ret += numberOfLeavesRE(node.left);
        }
        if (node.right != null) {
            ret += numberOfLeavesRE(node.right);
        }
        if (node.left == null && node.right == null) {
            return 1;
        }
        return ret;
    }

    public int heightOfTree() {
        return heightOfTreeRE(root) - 1;
    }

    private int heightOfTreeRE(BinaryNode<T> node) {
        if (node == null) {
            return 0;
        }
        return 1 + max(heightOfTreeRE(node.left), heightOfTreeRE(node.right));
    }

    public int numberOfNode() {
        return numberOfNodesRE(root) - 1;
    }

    private int numberOfNodesRE(BinaryNode<T> node) {
        if (node == null) {
            return 1;
        }
        return numberOfNodesRE(node.left) + numberOfNodesRE(node.right);
    }

    private static class BinaryNode<T extends Comparable<? super T>> {
        T element;
        BinaryNode<T> left;
        BinaryNode<T> right;

        public BinaryNode(T element, BinaryNode<T> left, BinaryNode<T> right) {
            this.element = element;
            this.left = left;
            this.right = right;
        }

        public BinaryNode(T element) {
            this.element = element;
            left = null;
            right = null;
        }
    }

    public boolean search (T t) {
        BinaryNode<T> current = root;
        while (true) {
            if (current.element.compareTo(t) > 0) {
                if (current.left == null) {
                    return false;
                }
                current = current.left;
            } else if (current.element.compareTo(t) < 0) {
                if (current.right == null) {
                    return false;
                }
                current = current.right;
            } else {
                return true;
            }
        }
    }
}